#pragma GCC optimize(2)
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <vector>

using namespace std;
using LL = long long;
const int N = 2e5 + 10;

int n;
string s;
bool st[N];
int cnt[N];
int q[N];

int main(){
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T--){
        int tt = -1;
        memset(cnt, 0, sizeof cnt);
        cin >> s;
        n = s.length();
        
        for(int i = 0; i < n; i ++){
            st[i] = false;
        }
        int lastNum = 9;
        for(int i = n - 1; i >= 0; i --){
            int cur = s[i] - '0';
            if(lastNum == cur) st[i] = true;
            else if(lastNum > cur) lastNum = cur, st[i] = true; 
        }

        for(int i = 0; i < n; i ++){
            if(!st[i]){
                int cur = s[i] - '0';
                cnt[min(cur + 1, 9)] ++;
            }
        }


        for(int i = 0; i < n; i ++){
            if(st[i]){
                int cur = s[i] - '0';
                q[++tt] = cur;
            }
        }

        for(int i = 0; i <= tt; i ++){
            cout << q[i];
            if(i != tt){
                int ne = q[i + 1];
                for(int j = q[i]; j <= ne; j ++){
                    for(int p = 1; p <= cnt[j]; p ++){
                        cout << j;
                    }
                    cnt[j] = 0;
                }
            }else{
                for(int j = q[i]; j <= 9; j ++){
                    for(int p = 1; p <= cnt[j]; p ++){
                        cout << j;
                    }
                    cnt[j] = 0;
                }
            }
        }


        cout << endl;
    }



    return 0;
}